//https://zhuanlan.zhihu.com/p/311113031
//https://leetcode.cn/problems/odd-even-linked-list/description/
//按奇偶位置拆分链表，得1->3->5->7->NULL和8->6->4->2->NULL
//反转偶链表，得1->3->5->7->NULL和2->4->6->8->NULL
//合并两个有序链表，得1->2->3->4->5->6->7->8->NULL

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (head == nullptr) {
            return head;
        }
        ListNode* evenHead = head->next;
        ListNode* odd = head;
        ListNode* even = evenHead;
        while (even != nullptr && even->next != nullptr) {
            odd->next = even->next;
            odd = odd->next;
            even->next = odd->next;
            even = even->next;
        }
        odd->next = evenHead;
        return head;
    }
};